package com.sk.leetcode.arithmetic;

/**
 * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 * 说明：不允许修改给定的链表。
 * 进阶：
 * 你是否可以不用额外空间解决此题？
 */
public class Test142 {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        // ListNode node1 = head.next = new ListNode(2);
        //node1.next = head;
        // ListNode node2 = node1.next = new ListNode(5);
        // ListNode node3 = node2.next = new ListNode(6);
        // node3.next = node1;
        ListNode node = detectCycle(head);
        System.out.println(node.val);
    }

    public static ListNode detectCycle(ListNode head) {
        if(head == null) {
            return null;
        }
        int index = 0;
        ListNode head0 = head.next;
        while (head0 != null) {
            index++;
            ListNode node = head;
            for (int i = 0; i < index; i++) {
                //先比较值在比较是否是相同对象，提高一定性能
                if(node.val == head0.val) {
                    if(node == head0) {
                        return head0;
                    }
                }
                node = node.next;
            }
            head0 = head0.next;
        }
        return null;
    }
}
